package com.shuang.tree7;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PreorderTraversal {
    //方法三：统一格式迭代法 （null标记法）
    public List<Integer> preorderTraversal(TreeNode root) {
        //前序遍历 中左右
        //定义集合用于封装数据
        List<Integer> result = new ArrayList<>();
        //判断 空的情况
        if (root == null) {
            return result;
        }

        //利用栈实现迭代法
        //入栈顺序 右左中 前序遍历 中左右
        //定义栈
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            //取出栈顶节点
            TreeNode node = stack.peek();
            if (node != null) {
                //栈顶元素不是空

                //弹出中节点避免重复操作
                stack.pop();

                //右不为空 入栈
                if (node.right != null) {
                    stack.push(node.right);
                }

                //左入栈
                if (node.left != null) {
                    stack.push(node.left);
                }

                //中入栈
                stack.push(node);
                // 中节点访问过，但是还没有处理，加入空节点做为标记
                stack.push(null);
            } else {
                //栈顶元素是空 证明下一个节点是标记过的节点 则可以将节点放到结果集中
                stack.pop(); // 将空节点弹出
                node = stack.pop(); // 重新取出栈中元素
                result.add(node.val); // 加入到结果集
            }

        }

        //循环结束返回封装结果
        return result;
    }

}
